package 我的Java学习_算法基础.day_06;

import java.util.Scanner;

public class _100_HDU_1576 {
    /**
     * 要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
     * Input
     * 数据的第一行是一个T，表示有T组数据。
     * 每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
     * Output
     * 对应每组数据输出(A/B)%9973。
     * Sample Input
     * 2
     * 1000 53
     * 87 123456789
     * Sample Output
     * 7922
     * 6060
     */

    /**
     * (A/B)%9973，求余，除法不满足交换律，可改写为B关于9973的逆元x
     * 这样结果等价于A*x%9973--x*A%9973---x*n%9973
     *Bx%9973==1
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i =0;i<T;i++){
            int n = sc.nextInt();
            int B = sc.nextInt();
            try{
                LinearEquation.inverseElement(B,9973);
                long x = LinearEquation.x;//x是B的关于9973的逆元
                System.out.println(x*n%9973);
            }catch (Exception e){
                e.printStackTrace();
            }
        }
    }
    private static class LinearEquation {
        static long x;
        static long y;
        public static long gcd(long m,long n){
            return n==0?m:gcd(n,m%n);
        }

        /**
         * 扩展欧几里得
         * 调用完成后x、y是ax+by=gcd(a,b)的解
         * @param a
         * @param b
         * @return 最大公约数
         */
        public static long ext_gcd(long a,long b){
            if(b==0){
                x=1;
                y=0;
                return a;
            }
            long res = ext_gcd(b,a%b);
            //x,y已经被下一层递归更新了
            long x1 = x;//备份x
            x=y;//更新x
            y=x1-a/b*y;//更新y
            return res;
        }
        /**
         * 求ax+by=m 的解
         * @param a
         * @param b
         * @param m
         * @throws Exception
         */
        public static long linearEquation(long a,long b,long m)throws Exception{
            long d = ext_gcd(a,b);
            //m不是gcd（a,b）的倍数，这个方程无解
            if(m%d!=0) throw new Exception("无解");
            long n = m/d;
            x*=n;
            y*=n;
            return d;
        }

        /**
         * 求逆元
         * ax%n=1中的x
         * @param a
         * @param mo
         * @return
         * @throws Exception
         */
        public static long inverseElement(long a,long mo) throws Exception{
            long d = LinearEquation.linearEquation(a,mo,1);
            x=(x%mo+mo)%mo;//保证x>0
            return d;
        }

    }
}
